Exponentiation conventionally means raising a number x to a power d, i.e., calculation of xd, which is equivalent to multiplying x by itself d−1 times. In this formula, x is referred to as the base, while d is the exponent. Modular exponentiation operations (i.e., calculation of xd mod N, wherein N is an integer called the modulus) in which d is a large integer (for example, 2048 bits long) are used in many cryptosystems, such Diffie-Hellmann secure key exchange, Rivest Shamir Adelman (RSA), ElGamal, and elliptic curve cryptography. A variety of exponentiation algorithms are known in the art, as described, for example, by Gordon in “A Survey of Fast Exponentiation Methods,” Journal of Algorithms 27, pages 129-146 (1998).
In more generalized mathematical terms, however, exponentiation may be understood as applying any associative binary operation (not only multiplication) between a given base x and itself d−1 times. The base may be a scalar or it may be any other data structure in a set to which the associative operation applies. For example, in elliptic curve cryptography, the basic operation is called addition rather than multiplication. Exponentiation in elliptic curve cryptography is therefore regarded as summing a point on an elliptic curve over a finite field with itself d−1 times, but it is still implemented by the same sort of computation. Therefore, the term “product” should be understood in the context of the present patent application and in the claims in this more generalized sense, to mean the result of any associative binary operation of the sort described above (such as addition of points on an elliptic curve); and the term “exponentiation” and the equivalent notation xd should likewise be understood in this generalized sense.
Exponentiation operations have generally been implemented in integrated circuits (including those used in cryptography) as sequences of squaring and multiplication operations. A number of methods have been developed for breaking cryptographic schemes by monitoring an integrated circuit during the exponentiation operation in order to extract the private key that is used in the circuit. These attacks include, for example, power analysis and fault attacks.
In recent years, attack-resistant methods of exponentiation have been developed. Examples of such methods are described by Joye and co-authors in the following publications:
“The Montgomery Powering Ladder,” Cryptographic Hardware and Embedded Systems—CHES 2002, published as vol. 2523 of Lecture Notes in Computer Science, pages 291-302 (Springer Verlag, 2003);
“Highly Regular m-ary Powering Ladders,” Selected Areas in Cryptography—SAC 2009, published as vol. 5867 of Lecture Notes in Computer Science, pages 350-363 (Springer Verlag, 2009); and
“Highly Regular Right-to-Left Algorithms for Scalar Multiplication,” Cryptographic Hardware and Embedded Systems—CHES 2007, published a vol. 4727 of Lecture Notes in Computer Science, pages 135-147 (Springer Verlag, 2007).
As another example, Byrne et al. describe an attack-resistant method for point multiplication in elliptic curve cryptography in “SPA Resistant Elliptic Curve Cryptosystem Using Addition Chains,” Fourth International Conference on Information Technology—ITNG'07 (2007), pages 995-1000. The method uses Euclid's addition chains to represent the number k of point multiplications.